package daily.year2024.m9;

import contest.year2022.m7.m7d9.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 二叉树
 *
 * @author wjs 2024/9/3
 */
public class d3 {
    //解法一：dfs
    class Solution1 {
        //node.goLeft = node.left.goRight + 1
        //node.goRight = node.right.goLeft + 1
        Map<TreeNode,Integer> goLeft, goRight;
        int res;
        public int longestZigZag(TreeNode root) {
            goLeft = new HashMap<>();
            goRight = new HashMap<>();
            res = 0;
            dfs(root);
            return res;
        }

        private void dfs(TreeNode node) {
            if(node == null) {
                return;
            }
            dfs(node.left);
            dfs(node.right);
            int gol = 0, gor = 0;
            if(node.left != null) {
                gol = goRight.get(node.left) + 1;
                res = Math.max(res,gol);
            }
            if(node.right != null) {
                gor = goLeft.get(node.right) + 1;
                res = Math.max(res,gor);
            }
            goLeft.put(node,gol);
            goRight.put(node,gor);
        }
    }

    //解法二：dfs，不使用map记录值
    class Solution2 {
        int res;
        public int longestZigZag(TreeNode root) {
            res = 0;
            dfs(root,true,0);
            dfs(root,false,0);
            return res;
        }
        private void dfs(TreeNode node, boolean fromRight, int len) {
            if(node == null) {
                return;
            }
            res = Math.max(res,len);
            if(fromRight) {
                dfs(node.left,false,len+1);
                dfs(node.right,true,1);
            } else {
                dfs(node.right,true,len+1);
                dfs(node.left,false,1);
            }
        }
    }
}
